# proevolytx@gmail.com
# 2012/9/24

# a lexer demo using automaton
# includes:
#   regex parser (regex -> syntax tree)
#   NFA generator (syntax tree -> NFA)
#   NFA simulator
#   NFA to DFA converter (NFA -> DFA)
#   DFA simulator
#   DFA minimizer (DFA -> minimized DFA)
# classes:
#   RegExpr: regex parser
#   FiniteAutomaton, Nfa, Dfa: support simualtion and conversion between
#     syntax tree -> NFA, NFA -> DFA, DFA -> minimized DFA

from copy import deepcopy
from stream import *
from struct import *

# output tree format
# {type:set, set:string}
# {type:or, left, right}
# {type:seq, left, right}
# {type:repetition, min, max, factor}
class RegExpr:
    CharLists = {
        "AlphaCap" : ("ABCDEFGHIJKLMNOPQRSTUVWXYZ", True),
        "AlphaNonCap" : ("abcdefghijklmnopqrstuvwxyz", True),
        "Digit" : ("0123456789", True),
        "Others" : (" #", False)}

    Quantities = {
        "*" : (0, "infinity"),
        "+" : (1, "infinity"),
        "?" : (0, 1)}

    EscapeChars = {"n":"\n", "t":"\t", "r":"\r", "\\":"\\",
                   "[":"[", "]":"]", "(":"(", ")":")",
                   "|":"|", "*":"*", "+":"+", "?":"?",
                   "-":"-"}
    
    def __init__(s, stream):
        s.stream = stream

    def FindList(s, ch):
        for listName in s.CharLists:
            if ch in s.CharLists[listName][0]:
                return listName
        if not ch.isspace():
            return "Others"

    def Match(s, string):
        length = len(string)
        peek = s.stream.Peek(length)
        if peek == string:
            s.stream.Next(length)
        else:
            raise Exception(string + " expected, but " + peek + " instead")

    def SingleChar(s):
        peek = s.stream.Peek()
        if peek == "\\":
            s.stream.Next()
            peekNext = s.stream.Peek()
            if peekNext not in s.EscapeChars:
                raise Exception("Invalid escape char : " + peek + peekNext)
            s.stream.Next()
            return {"type":"char", "char":s.EscapeChars[peekNext],
                    "list":"Others"}
        else:
            chlist = s.FindList(peek)
            if chlist is None:
                raise Exception("Invalid char : " + peek)
            else:
                s.stream.Next()
                return {"type":"char", "char":peek, "list":chlist}

    def SingleCharSet(s):
        ch = s.SingleChar()
        return {"type":"set", "set":ch["char"]}

    def CharRange(s):
        chlt = s.SingleChar()
        if s.stream.Peek() == "-":
            s.Match("-")
            chrt = s.SingleChar()
            listlt = chlt["list"]
            listrt = chrt["list"]
            if listlt != listrt or not s.CharLists[listlt][1]:
                raise Exception(
                    "Invalid range from " + chlt["char"] + " to " + chrt["char"])
            else:
                chlist = s.CharLists[listlt][0]
                beg = chlist.find(chlt["char"])
                end = chlist.find(chrt["char"])
                if beg > end:
                    beg, end = end, beg
                return {"type":"set", "set":chlist[beg : end + 1]}
        else:
            return {"type":"set", "set":chlt["char"]}

    @staticmethod
    def CombineCharSet(cs1, cs2):
        result = ""
        for ch in cs1 + cs2:
            if result.find(ch) < 0:
                result += ch
        return result

    def CharSet(s):
        s.Match("[")
        result = ""
        while True:
            peek = s.stream.Peek()
            if peek is None:
                raise Exception("Char set ends without ]")
            if peek == "]":
                s.stream.Next()
                break
            r = s.CharRange()
            result = s.CombineCharSet(result, r["set"])
        return {"type":"set", "set":result}

    def Factor(s):
        peek = s.stream.Peek()
        if peek == "(":
            s.Match("(")
            result = s.Expr()
            s.Match(")")
            return result
        elif peek == "[":
            return s.CharSet()
        else:
            return s.SingleCharSet()

    def ExprMono(s):
        factor = s.Factor()
        peek = s.stream.Peek()
        if peek in ["*", "+", "?"]:
            s.stream.Next()
            result = {
                "type" : "repetition",
                "factor" : factor,
                "min" : s.Quantities[peek][0],
                "max" : s.Quantities[peek][1]}
            return result
        else:
            return factor

    def ExprSeq(s):
        left = s.ExprMono()
        while s.stream.Peek() not in [None, "|", "*", "+", "?", ")"]:
            right = s.ExprMono()
            left = {
                "type" : "seq",
                "left" : left,
                "right" : right}
        return left

    def ExprOr(s):
        left = s.ExprSeq()
        while s.stream.Peek() == "|":
            s.Match("|")
            right = s.ExprSeq()
            if left["type"] == "set" and right["type"] == "set":
                left = {
                    "type" : "set",
                    "set" : s.CombineCharSet(left["set"], right["set"])}
            else:
                left = {
                    "type" : "or",
                    "left" : left,
                    "right" : right}
            
        return left

    def Expr(s):
        return s.ExprOr()

    @staticmethod
    def Print(root, indent = ""):
        if "omit" in root:
            print indent + "omitable"
        if root["type"] == "set":
            print indent + "any in " + repr("".join(sorted(root["set"])))
        elif root["type"] == "or":
            print indent + "or"
            print indent + "  left"
            RegExpr.Print(root["left"], indent + "    ")
            print indent + "  right"
            RegExpr.Print(root["right"], indent + "    ")
        elif root["type"] == "seq":
            RegExpr.Print(root["left"], indent)
            RegExpr.Print(root["right"], indent)
        elif root["type"] == "repetition":
            print indent + "repetition in [" + \
                  str(root["min"]) + ", " + str(root["max"]) + "]"
            RegExpr.Print(root["factor"], indent + "  ")
        else:
            raise Exception("Invalid node type")

# nfm format:
# begin:id, end:[idlist]
# edges:[edgelist]
# edge {begin:id, end:id, cond:str, epsilon:bool}
class FiniteAutomaton:
    def __init__(s):
        s.begin = 0
        s.end = [0]
        s.edges = []
        s.current = []
        
    def AddEdge(s, beg, end, cond, epsilon = False):
        edgelist = s.GetEdges(beg, end)
        if not edgelist:
            s.edges.append({"begin":beg, "end":end, "cond":cond, "e":epsilon})
        else:
            assert len(edgelist) == 1
            edge = edgelist[0]
            edge["cond"] = RegExpr.CombineCharSet(edge["cond"], cond)
            edge["cond"] = "".join(sorted(edge["cond"]))
            if epsilon: edge["e"] = True
           
    def DelEdge(s, beg, end):
        if not s.GetEdges(beg, end):
            s.edges.remove({"begin":beg, "end":end})
    
    def GetEdges(s, beg = None, end = None):
        result = []
        for e in s.edges:
            if (e["begin"] == beg or beg is None) and \
               (e["end"] == end or end is None):
                result.append(e)
        return result
    
    def Rearrange(s, offset = 0):
        nodes = set()
        for e in s.edges:
            nodes.add(e["begin"])
            nodes.add(e["end"])
            
        sortedNodes = sorted(list(nodes))
        
        for i, n in enumerate(sortedNodes):
            for e in s.edges:
                if e["begin"] == n : e["begin"] = i
                if e["end"] == n : e["end"] = i
        for e in s.edges:
            e["begin"] += offset
            e["end"] += offset
                
        s.begin = sortedNodes.index(s.begin) + offset
        newend = []
        for end in s.end:
            newid = sortedNodes.index(end) + offset
            newend.append(newid)
        s.end = newend
        
        return sortedNodes
    
    def ExpandNode(s, node, machine):
        machine = deepcopy(machine)
        sortedNodes = s.Rearrange()
        nodeId = sortedNodes.index(node)
        if nodeId < 0:
            raise Exception("Node " + str(node) + " not exist")

        machineNodes = machine.Rearrange(len(sortedNodes))
        if len(machine.end) > 1:
            newend = len(machineNodes) + len(sortedNodes)
            for e in machine.end:
                machine.AddEdge(e, newend, None)
            machine.end = [newend]
        
        for e in machine.edges:
            s.edges.append(e)

        beg = machine.begin
        end = machine.end[0]
        for e in s.edges:
            if e["end"] == nodeId: e["end"] = beg
            if e["begin"] == nodeId: e["begin"] = end
        if s.begin == nodeId: s.begin = beg
        newend = []
        for e in s.end:
            if e == nodeId:
                newend.append(end)
            else:
                newend.append(e)
        s.end = newend
        s.Rearrange()

    def GetEpsilonClosure(s, states):
        result = []
        for st in states:
            if st in result: continue
            q = [st]
            result.append(st)
            while len(q) > 0:
                front = q[0]
                q = q[1:]
                edges = s.GetEdges(front, None)
                for e in edges:
                    if e["end"] in result: continue
                    if not e["e"]: continue
                    q.append(e["end"])
                    result.append(e["end"])
        return set(result)

    def GetReachableStates(s, states, ch):
        result = set()
        for st in states:
            edges = s.GetEdges(st, None)
            for e in edges:
                if ch in e["cond"]:
                    arrive = s.GetEpsilonClosure([e["end"]])
                    result = result.union(arrive)
        return result

    def GetCharSet(s):
        chars = ""
        for e in s.edges:
            chars = RegExpr.CombineCharSet(chars, e["cond"])
        return chars

    def Reset(s):
        s.current = set([s.begin])

    def IsAccepted(s):
        return len(s.current.intersection(s.end)) > 0

    def IsDead(s):
        return len(s.current) == 0

    def Print(s):
        print "start state:", s.begin
        print "finish states:", s.end
        print "edges:"
        for e in s.edges:
            print "\t", e

class Nfa(FiniteAutomaton):
    def Simulate(s, stream):
        s.current = s.GetEpsilonClosure(s.current)
        while stream.Peek():
            peek = stream.Peek()
            stream.Next()
            s.current = s.GetReachableStates(s.current, peek)
            s.current = s.GetEpsilonClosure(s.current)
        return s.current

    @staticmethod
    def GenerateNfa(root):
        if root["type"] == "set":
            fm = Nfa()
            fm.AddEdge(0, 1, root["set"])
            fm.begin = 0
            fm.end = [1]
            return fm
        
        elif root["type"] == "or":
            fm = Nfa()
            fm.AddEdge(0, 1, "", True)
            fm.AddEdge(0, 2, "", True)
            fm.AddEdge(1, 3, "", True)
            fm.AddEdge(2, 3, "", True)
            fm.begin = 0
            fm.end = [3]
            left = Nfa.GenerateNfa(root["left"])
            right = Nfa.GenerateNfa(root["right"])
            fm.ExpandNode(2, right)
            fm.ExpandNode(1, left)
            return fm
        
        elif root["type"] == "seq":
            fm = Nfa()
            fm.AddEdge(0, 1, "", True)
            fm.begin = 0
            fm.end = [1]
            left = Nfa.GenerateNfa(root["left"])
            right = Nfa.GenerateNfa(root["right"])
            fm.ExpandNode(1, right)
            fm.ExpandNode(0, left)
            return fm
        
        elif root["type"] == "repetition":
            fm = Nfa()
            for i in range(root["min"]):
                fm.AddEdge(i, i + 1, "", True)
                
            if root["max"] == "infinity":
                n = root["min"] + 1
                fm.AddEdge(n - 1, n, "", True)
                fm.AddEdge(n, n + 1, "", True)
                fm.AddEdge(n, n, "", True)
                fm.AddEdge(n - 1, n + 1, "", True)
            else:
                n = root["max"]
                for i in range(root["min"], n):
                    fm.AddEdge(i, i + 1, "", True)
                    fm.AddEdge(i, n + 1, "", True)
                fm.AddEdge(n, n + 1, "", True)
                
            fm.begin = 0
            fm.end = [n + 1]
            
            factor = Nfa.GenerateNfa(root["factor"])
            
            for i in range(n, 0, -1):
                fm.ExpandNode(i, factor)
                
            return fm

class Dfa(FiniteAutomaton):
    def Simulate(s, stream):
        while stream.Peek():
            peek = stream.Peek()
            stream.Next()
            s.current = s.GetReachableStates(s.current, peek)
            if len(s.current) == 0:
                return []
            elif len(s.current) > 1:
                raise Exception("Not Dfa")
        return s.current

    def Minimize(s):
        nodeCount = len(s.Rearrange())
        
        groups = [[None, []], [None, []]]
        for i in range(nodeCount):
            if i in s.end:
                groups[0][1].append(i)
            else:
                groups[1][1].append(i)
        
        chars = s.GetCharSet()

        for ch in chars:
            newgroups = []
            for group in groups:
                groupsToAppend = []
                for state in group[1]:
                    to = s.GetReachableStates([state], ch)
                    found = None
                    for g in groupsToAppend:
                        if set(g[0]) == set(to):
                            found = g
                            break
                    if not found:
                        found = [to, []]
                        groupsToAppend.append(found)
                    found[1].append(state)
                newgroups += groupsToAppend
            groups = newgroups

        for g in groups:
            reserved = g[1][0]
            for state in g[1][1:]:
                for e in s.edges:
                    if e["begin"] == state: e["begin"] = reserved
                    if e["end"] == state: e["end"] = reserved
                if s.begin == state: s.begin = reserved
                if state in s.end:
                    s.end.remove(state)
                    if reserved not in s.end:
                        s.end.append(reserved)
        edges = s.edges
        s.edges = []
        for e in edges:
            s.AddEdge(e["begin"], e["end"], e["cond"])
        
        s.Rearrange()

        # remove unreachable states
        q = deepcopy(s.end)
        good = set()
        while q:
            front = q[0]
            q = q[1:]
            if front in good:
                continue
            good.add(front)
            edges = s.GetEdges(None, front)
            for e in edges:
                if e["begin"] not in q:
                    q.append(e["begin"])
        edges = s.edges
        s.edges = []
        for e in edges:
            if e["begin"] in good and e["end"] in good:
                s.edges.append(e)
        s.Rearrange()

    @staticmethod
    def GenerateDfa(nfa):
        chars = nfa.GetCharSet()
        dfa = Dfa()
        dfa.begin = 0
        dfa.end = []

        q = [nfa.GetEpsilonClosure([nfa.begin])]
        front = 0
        rear = 1
        while front < rear:
            cur = q[front]
            front += 1
            #print "front", front
            for ch in chars:
                #print "ch", ch
                new = nfa.GetReachableStates(cur, ch)
                new = nfa.GetEpsilonClosure(new)
                if new not in q:
                    q.append(new)
                    if new.intersection(nfa.end):
                        dfa.end.append(rear)
                    dfa.AddEdge(front - 1, rear, ch)
                    rear += 1
                    #print "rear", rear
                else:
                    index = q.index(new)
                    dfa.AddEdge(front - 1, index, ch)
        return dfa

class StaticDfa:
    # fh: file handle
    def Load(s, fh):
        # load s.begin
        data = fh.read(4)
        s.begin = unpack("l", data)[0]

        # load s.end
        data = fh.read(4)
        cnt = unpack("l", data)[0]
        s.end = set()
        for i in range(cnt):
            data = fh.read(4)
            end = unpack("l", data)[0]
            s.end.add(end)

        # load s.edges
        data = fh.read(4)
        cnt = unpack("l", data)[0]
        s.edges = {}
        for i in range(cnt):
            data = fh.read(12)
            ch, beg, end = unpack("cll", data)
            if ch not in s.edges:
                s.edges[ch] = {}
            s.edges[ch][beg] = end

    # fh: file handle
    def Save(s, fh):
        # save s.begin
        data = pack("l", s.begin)
        fh.write(data)

        # save s.end
        data = pack("l", len(s.end))
        fh.write(data)
        for end in s.end:
            data = pack("l", end)
            fh.write(data)

        # save s.edges:
        edges = []
        for ch in s.edges:
            for beg in s.edges[ch]:
                edges.append((ch, beg, s.edges[ch][beg]))
        data = pack("l", len(edges))
        fh.write(data)
        for e in edges:
            data = pack("cll", e[0], e[1], e[2])
            fh.write(data)
    
    def Reset(s):
        s.current = s.begin
    
    def Simulate(s, stream):
        while stream.Peek():
            peek = stream.Peek()
            stream.Next()
            s.current = s.GetReachableState(s.current, peek)
            if s.current is None:
                return []
        return [s.current]

    def GetReachableState(s, state, ch):
        if ch in s.edges:
            chedges = s.edges[ch]
        else:
            return None

        if state in chedges:
            return chedges[state]
        else:
            return None

    def IsDead(s):
        return s.current == None

    def IsAccepted(s):
        if s.current and s.current in s.end:
            return True
        else:
            return False
        
    @staticmethod
    def FromDfa(dfa):
        res = StaticDfa()
        res.begin = dfa.begin
        res.end = set(dfa.end)
        res.edges = {}
        for e in dfa.edges:
            for ch in e["cond"]:
                if ch not in res.edges:
                    res.edges[ch] = {}
                chedges = res.edges[ch]
                    
                key = e["begin"]
                chedges[key] = e["end"]
                
        return res

# test engine
if __name__ == "__main__":
    
    regex = "(\\+|\\-)?(0|[1-9][0-9]*)(.[0-9]+)?"
    print "\n*** REGULAR EXPRESSION ***\n"
    print regex

    stream = StringStream(regex)
    parser = RegExpr(stream)
    tree = parser.Expr()
    
    print "\n*** EXPRESSION SYNTAX TREE ***\n"
    RegExpr.Print(tree)

    nfa = Nfa.GenerateNfa(tree)
    print "\n*** NFA ***\n"
    nfa.Print()

    dfa = Dfa.GenerateDfa(nfa)
    print "\n*** DFA ***\n"
    dfa.Print()

    mindfa = deepcopy(dfa)
    mindfa.Minimize()
    print "\n*** Minimized DFA ***\n"
    mindfa.Print()

    sdfa = StaticDfa.FromDfa(mindfa)

    testcases = ["0", "123", "0123", "+123", "-023",
                 "123.", "123.4", "+123.456", "-0123.456",
                 "+.123", "0.0", "-1", ""]
    for i, test in enumerate(testcases):
        print "\n*** TEST CASE " + str(i + 1) + " ***\n"
        print "input:\t" + test

        nfa.Reset()
        result = nfa.Simulate(StringStream(test))
        print "NFA:"
        print "\tfinishing in states:", sorted(result)
        if nfa.IsAccepted():
            print "\taccepted"
        else:
            print "\tunaccepted"

        dfa.Reset()
        result = dfa.Simulate(StringStream(test))
        print "DFA:"
        print "\tfinishing in states:", sorted(result)
        if dfa.IsAccepted():
            print "\taccepted"
        else:
            print "\tunaccepted"

        mindfa.Reset()
        result = mindfa.Simulate(StringStream(test))
        print "Minimized DFA:"
        print "\tfinishing in states:", sorted(result)
        if mindfa.IsAccepted():
            print "\taccepted"
        else:
            print "\tunaccepted"

        sdfa.Reset()
        result = sdfa.Simulate(StringStream(test))
        print "Static Minimized DFA:"
        print "\tfinishing in states:", sorted(result)
        if sdfa.IsAccepted():
            print "\taccepted"
        else:
            print "\tunaccepted"

    print "\n*** DONE ***\n"
